#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=1050;
long long a[MAXN];
void init(){
    a[0]=1;
    a[1]=0;
    for(int i=2;i<=1000;i++){
        a[i]=(2*a[i-2]+a[i-1])%10000;
    }
}
int main(void){
    int n;
    init();
    while(~scanf("%d",&n) && n){
        printf("%lld\n",a[n]);
    }
    return 0;
}
